This invention relates to a logic circuit for implementing binary multiplication by a constant fraction and to a method of deriving a binary logic circuit for performing such multiplication.
When designing integrated circuits, logic is often required to perform addition, subtraction, multiplication and division. Whilst addition, subtraction and multiplication operations can all be cheaply implemented in hardware, division is acknowledged to be an expensive operation to implement in hardware.
In the case that the divisor is known to be a constant at design-time, a division operation can be expressed as multiplication by a constant fraction and it is possible to construct efficient implementations of the division operation using a combination of addition and constant multiplication logic. This can significantly simplify the logic and hence reduce the area of integrated circuit needed to implement the division operation. For example, if the division operation
      px    q    ,where p and q are integer constants and x is an integer variable, can be rewritten in the form
            ax      +      b              2      k        ,then the division operation can be expressed in logic as a multiply-add operation whose result is right-shifted by k binary places. However, there are an infinite number of values of a, b and k which satisfy this equation, some of which provide less efficient expressions in logic than others.
US Patent Application 2013/0103733, which is incorporated by reference in its entirety, discloses techniques for deriving values for a, b and k for use in designing integrated circuit logic, but does not describe logic optimally configured according to the most efficient expression of multiplication by a constant fraction. Suboptimal expressions of division logic, even those embodied as a multiply-add operation, are overly complex and consume a greater area of integrated circuit than necessary.